class Trie {
  constructor() {
    this.root = Object.create(null)
    this.endOfWord = Symbol('endOfWord')
  }
  insert(word) {
    let node = this.root

    for (let w of word) {
      if (!node[w]) {
        node[w] = Object.create(null)
      }
      node = node[w]
    }

    if (!node[this.endOfWord]) {
      node[this.endOfWord] = 0
    }

    node[this.endOfWord] += 1
  }
  most() {
    let max = 0
    let maxWord = null
    let _this = this
    function visit(node, str) {
      //   console.log(_this)
      if (node[_this.endOfWord] && node[_this.endOfWord] > max) {
        max = node[_this.endOfWord]
        maxWord = str
      }

      for (let v of Object.keys(node)) {
        visit(node[v], str + v)
      }
    }

    visit(this.root, '')
    // console.log(max, maxWord)

    return { max, maxWord }
  }
  search(word) {
    let node = this.root
    for (let w of word) {
      if (!node[w]) {
        return false
      }
      node = node[w]
    }
    return !!node[this.endOfWord]
  }
  startsWith(prefix) {
    let node = this.root
    for (let w of prefix) {
      if (!node[w]) {
        return false
      }
      node = node[w]
    }
    return true
  }
}

function randomWord(length) {
  let s = ''
  for (let i = 0; i < length; i++) {
    s += String.fromCharCode(Math.random() * 26 + 'a'.charCodeAt(0))
  }
  return s
}

let trie = new Trie()

for (let i = 0; i < 10000; i++) {
  trie.insert(randomWord(4))
}

// let most = trie.most()

// console.log(trie, most)

// String.prototype.startWith()
function startWith(string, prefix) {
  let preLength = prefix.length
  for (let i = 0; i < preLength; i++) {
    if (string[i] !== prefix[i]) return false
  }
  return true
}

startWith('abc', 'ab')

// String.prototype.endsWith()
function endsWith(string, postfix) {
  let postLength = postfix.length
  for (let i = postLength - 1; i >= 0; i--) {
    if (string[i] !== postfix[i]) return false
  }
  return true
}
// String.prototype.includes()
function includes(string, substring) {
  let start = 0
  let stringLength = string.length
  let subLength = substring.length
  for (let i = 0; i < stringLength; i++) {
    if (string[i] === substring[0]) {
      start = i
      break
    }
  }
  if (!start || stringLength - start < subLength) return false // bug !start
  for (let i = start; i < stringLength; i++) {
    if (string[i] !== substring[i - start]) return false
  }
  return true
}
